#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <set>
#include <string.h>
#include <cmath>

using namespace std;


vector<vector<int>> threesum(vector<int> & num)
{
	//sort num
	sort(num.begin(),num.end());
	vector<vector<int>> vresult;
	if(num.at(0)>0 || num.at(num.size()-1)<0){
		return vresult;
	}

	//int mid = (num.size()-1)/2;
	int i,j,k=num.size()-1;

	//vector<vector<int>> vresult;
	//for(i = 0, j=num.size()-1; i!=mid,j!=mid;)
	//{
	//	if((num.at(i)+num.at(mid)+num.at(j))>0){
	//		j--;
	//		if((j)==mid && i+1<mid)
	//		{
	//			mid--;
	//			j=num.size()-1;
	//		}
	//	}
	//	else if((num.at(i)+num.at(mid)+num.at(j))<0){
	//		i++;
	//		if(i==mid && mid<j-1){
	//			mid++;
	//			i=0;
	//		}
	//	}
	//	else
	//	{
	//		vector<int> v;
	//		v.push_back(num[i]);
	//		v.push_back(num[mid]);
	//		v.push_back(num[j]);
	//		vresult.push_back(v);
	//		if((i+1)==mid && mid < j-1){
	//			mid++;
	//			i++;
	//			continue;
	//		}
	//		//return vresult;
	//	}
	//}

	if(num.size()==3)
	{
		if(num[0]+num[1]+num[2]==0)
		{
			vresult.push_back(num);
			return vresult;
		}
	}
	else if(num.empty() || num.size()<3)
	{
		return vresult;
	}
	else if(num[0]>=0 || num[num.size()-1]<=0)
	{
		if(num[0]==0 && num[num.size()-1]==0)
		{
			vector<int> v(3);
			vresult.push_back(v);
		}
		return vresult;
	}



	for(i=0;num[i]<=0;)
	{
		/*for(j=i+1;j<k;)
		{
		}*/
		j = i+1;
		k=num.size()-1;
		for(;k>j;)
		{
			if(num[i]+num[j]+num[k] < 0 )
			{
				j++;
			}
			else if(num[i]+num[j]+num[k] > 0 )
			{
				k--;
			}
			else
			{
				int count1=1;
				int count2=1;

				vector<int> v;
				v.push_back(num[i]);
				v.push_back(num[j]);
				v.push_back(num[k]);
				vresult.push_back(v);

				int temp1=j,temp2=k;
				while(num[temp1+1] == num[temp1] && temp1 < temp2)
				{
					count1++;
					temp1++;
				}
				while(num[temp2-1] == num[temp2] && temp2>temp1)
				{
					count2++;
					temp2--;
				}
				j += count1;
				k -= count2;

			}
		}
		int count=1;
		int temp =i;
		while(num[temp+1] == num[temp] )
		{
			temp++;
			count++;
		}

		i+= count;
	}
	return vresult;
}




vector<vector<int>> foursum(vector<int>& num, int target)
{
	sort(num.begin(),num.end());
	vector<vector<int>> result;
	if(num.size()<4)
	{
		return result;
	}

	if(num.size()==4)
	{
		if(num[0]+num[1]+num[2]+num[3] == target)
		{
			result.push_back(num);
		}
		return result;
	}


	//handle more than 4 elements
	int i,j,k,l;
	for(i=0; i<=num.size()-4;)
	{
		l = num.size()-1;
		for(j=i+1;j<l-1;)
		{
			l=num.size()-1;
			for(k=j+1;k<l;)
			{
				if(num[i]+num[j]+num[k]+num[l] < target )
				{
					k++;
				}
				else if(num[i]+num[j]+num[k]+num[l] > target )
				{
					l--;
				}
				else
				{
					vector<int> v;
					v.push_back(num[i]);
					v.push_back(num[j]);
					v.push_back(num[k]);
					v.push_back(num[l]);

					result.push_back(v);

					//update k,l
					if(k+1 == l || k+1==l-1)
					{
						break;
					}
					int temp1=k,temp2=l;
					int count1=1,count2=1;
					while(num[temp1+1] == num[temp1] && temp1 < temp2)
					{
						count1++;
						temp1++;
					}
					while(num[temp2-1] == num[temp2] && temp2>temp1)
					{
						count2++;
						temp2--;
					}
					k += count1;
					l -= count2;

				}
			}

			//update j
			int count =1;
			int temp = j;
			while(num[temp+1]==num[temp])
			{
				count++;
				temp++;
			}
			j+=count;
		}

		//update i
		int count =1;
		int temp = i;
		while(num[temp+1]==num[temp])
		{
			count++;
			temp++;
		}
		i+=count;
	}

	return result;

}





set<vector<int> > find_triplets(vector<int>& arr) {
	sort(arr.begin(), arr.end());
	set<vector<int> > triplets;
	vector<int> triplet(3);
	int n = arr.size();
	for (int i = 0;i < n; i++) {
		int j = i + 1;
		int k = n - 1;
		while (j < k) {
			int sum_two = arr[i] + arr[j];
			if (sum_two + arr[k] < 0) {
				j++;
			} else if (sum_two + arr[k] > 0) {
				k--;
			} else {
				triplet[0] = arr[i];
				triplet[1] = arr[j];
				triplet[2] = arr[k];
				triplets.insert(triplet);
				j++;
				k--;
			}
		}
	}
	return triplets;
}

int power(int base ,int exponent)
{
	//assert( base == 0);
	if(!exponent)
	{
		return 1;
	}
	int result=1;
	while(exponent)
	{
		result *= base;
		exponent--;
	}
	return result;
}


void itoa_min(int value, char* istring, int radix)
{
	if(value<0)
		*istring++ = '-';

	//digits
	int num_digits = 0;
	int temp = value;
	
	while(temp)
	{
		temp /=radix;
		num_digits++;
	}
	if(!value)
		num_digits++;
	istring[num_digits]='\0';

	//fill in the string
	while(num_digits>0)
	{
		int remainder = value%radix;
		//update value
		value/=radix;

		char asiccdigit;

		if(remainder<10)
			asiccdigit = '0'+remainder;
		else
			asiccdigit = 'a' + remainder;
		istring[num_digits-1] =asiccdigit;
		--num_digits;
	}
}

string addbinary(string a, string b)
{
	long a_int = atol(a.c_str());
	long b_int = atol(b.c_str());
	
	int bits = (a.size() >= b.size())? a.size() : b.size();
	//char *buf = new char[bits+1];
	//buf[bits+1]='\0';
	long result = a_int+b_int;
	int i= 0;
	bool bcarried = false;
	char asicdigit;
	//int head= (result/power(10,bits-1))%10;
	while(i<bits)
	{
		int ibit = (result/power(10,i))%10;

		if(ibit >= 2)
		{
			bcarried = true;
			result += power(10,i+1);
			result -= 2*power(10,i);
		}
		else
		{
			bcarried = false;
		}
		
		//asicdigit = '0'+ibit%2;
		//buf[bits-i]=asicdigit;
		i++;


	}

	//itoa_min(result,buf,10);
	char* buff=NULL;
	int nsize;
	if(bcarried)
	{
		buff = new char[i+2];
		nsize = i+2;
	}
	else
	{
		buff = new char[i+1];
		nsize = i+1;

	}
	//int nsize = strlen(buff);

	buff[nsize-1] = '\0';
	long temp = result;
	while (nsize)
	{
		int remainder = temp%10;
		temp /= 10;
		asicdigit = '0'+remainder;
		buff[nsize-2] = asicdigit;
		--nsize;
	}


	
	return string(buff);


}



string AddBinary(string s1, string s2) 
{
	int len1 = s1.size()-1;
	int len2 = s2.size()-1;
	string s = len1 > len2? s1 : s2;
	int len = s.size()-1;
	char carry = '0';

	while(len1 >=0 && len2 >=0)
	{
		s[len] = (s1[len1] ^ s2[len2] ^ carry);
		carry = s1[len1] & s2[len2] | carry & s1[len1] |  carry & s2[len2];

		--len, --len1, --len2;
	}

	while(len1 >= 0)
	{
		s[len] = (s1[len1] ^ carry) + '0';
		carry = s1[len1] & carry;
		--len, --len1;
	}

	while(len2 >= 0)
	{
		s[len] = (s2[len2] ^ carry) + '0';
		carry = s2[len2] & carry;
		--len, --len2;
	}


	if (carry ^ '0') //if carry is '1', insert carry 
		s.insert(s.begin(), carry);

	return s;
}






int kthvalue(vector<int>& a, vector<int>& b, int k)
{
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());


	int a_offset=0;
	int b_offset=0;

	if(a.size()+b.size() < k) { return -9999;}
	while(1)
	{
		if(a_offset < a.size() )
		{
			while(b_offset == b.size()-1 || a[a_offset] <= b[b_offset])
			{
				a_offset++;
				if(a_offset+b_offset == k-1)
					return a[a_offset];
			}
		}

		if(b_offset < b.size() )
		{
			while(a_offset == a.size()-1 || b[b_offset] <= a[a_offset])
			{
				b_offset++;
				if(a_offset+b_offset== k-1)
					return b[b_offset];
			}
		}
	}
}





int main()
{
	/*unsigned int v;
	cin>>v;
	unsigned int r = v;

	int s= sizeof(v)*8 -1;

	for(v>>=1;v;v>>=1){
		r <<= 1;
		r |= v&1;
		s--;
	}
	r<<=s;

	cin.get();*/
	int a[] = {0,8,-2,-4,9,0,-2,-5,-1,-5,0,4,-9,8};
	vector<int> num(&a[0],&a[sizeof(a)/sizeof(int) ]);
	//vector<int> num1(&b[0],&b[sizeof(a)/sizeof(int)]);
	
	//int ret = kthvalue(num,num1,4);

	//int bret = 7/2;

	char buf[10];
	int val = 1100;
	//itoa_min(val,buf,10);
	
	//set<vector<int>> irest = find_triplets(num);
	//vector<vector<int> > irest = threesum(num);
	//vector<vector<int> > irest = foursum(num,29);

	AddBinary("1111111111111111111111111111111110","1");
	
	return 0;
}